Міністерство Освіти і Науки України Національний Університет “Львівська Політехніка”
Кафедра ЕОМ Елементи абстрактної алгебри Методичні вказівкидо практичних занять та самостійної роботи з курсу “Дискретна математика”для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” Затвердженона засіданні кафедриЕлектронних Обчислювальних МашинПротокол № 6 від 21 січня 2003 року Львів – 2003 Алгебри та операції : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 15 с. Укладачі: Р. Попович, к.т.н., доцент І. Мороз, асистент Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н. Юрчак І. Ю., доцент кафедри САПР, к. т. н. Вступ Основу сучасних швидких та якісних технологій обробки інформації становлять комп’ютери – від персональних до супер-ЕОМ. Подання інформації для ЕОМ дискретне, і її обробка складається з послідовностей елементарних перетворень тих чи інших інформаційних одиниць (слів, літер, цифр тощо). Тобто, фундаментальною ідеєю щодо відображення реального світу в комп’ютері є ідея дискретизації об’єктів. Для ефективної застосування комп’ютерів необхідно навчитися будувати моделі реальних об’єктів та процесів їх перетворення. Досить часто такими моделями можуть бути конструкції дискретної математики, зокрема, такі, як алгебраїчні структури, що розглядаються в даних методичних вказівках. Під абстрактною оболонкою більшості аксіоматичних теорій алгебри ховаються цілком конкретні задачі прикладного характеру. Складна взаємодія теоретичних і прикладних аспектів теорії, яка притаманна всій математиці, в алгебрі проявляється дуже виразно. Наведемо кілька прикладів практичного використання алгебраїчних структур – множин з алгебраїчними операціями. Однією з галузей застосування є кодування інформації при передачі через канал зв’язку. При цьому ставиться вимога забезпечити виправлення помилок, які виникають внаслідок фізичних завад у каналах зв’язку або пристроях зберігання інформації. Це досягається шляхом введення при кодуванні надлишковості, яка дозволяє так вибрати множини символів для передачі, щоб вони задовольняли додатковим умовам, перевірка яких після прийому дає можливість виявити й виправити помилки. Найкращих результатів досягнуто, коли символи, що передаються, розглядаються як елементи певних алгебраїчних структур, зокрема скінченних полів (полів Галуа). При цьому простими стають процедури кодування й декодування, зменшується ймовірність неправильного декодування даних (циклічні коди, коди Ріда-Соломона тощо). Іншою галуззю застосування є криптографія: захист інформації шляхом її перетворення, що виключає прочитання цієї інформації сторонньою особою. Ще кілька десятиліть тому такий підхід стосувався в основному військових операцій або був пов’язаний з шпигунськими історіями, а не був предметом широкого використання. Причиною бурхливого розвитку криптографії є широке використання комп'ютерних мереж, зокрема глобальної мережі Internet, якими передаються великі обсяги інформації державного, військового, комерційного й приватного характеру, що не допускає можливості доступу до неї сторонніх осіб. При виконанні сучасних алгоритмів шифрування з таємним ключем використовуються алгебраїчні структури скінчених полів (наприклад, стандарт AES симетричного шифрування США). Широко вживаний алгоритм RSA шифрування з відкритим ключем (багато провідних світових ІТ-компаній вклали в його розвиток значні кошти, він стоїть в основі функціонування Internet - платежів eMoney) ґрунтується на алгебраїчному понятті фактор-кільця кільця цілих чисел за модулем великого натурального числа. Алгебраїчні операції Нехай Х – довільна множина. n-арною операцією на множині Х називається відображення f: Хn ( Х, яке кожному вектору (x1, x2, …, xn) ( Хn ставит...